package com.wujunshen.algorithm.leetcode.basic;

import java.util.HashMap;
import java.util.Map;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/24 00:41<br>
 */
public class 最小覆盖子串 {
  public static String minWindow(String s, String p) {
    String ans = "";
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < p.length(); i++) {
      map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
    }

    int i = 0;
    int j = 0;
    int max = Integer.MAX_VALUE;
    int count = map.size();

    while (j <= s.length()) {
      if (count != 0) {
        if (j < s.length() && map.containsKey(s.charAt(j))) {
          map.replace(s.charAt(j), map.get(s.charAt(j)) - 1);
          if (map.get(s.charAt(j)) == 0) {
            count--;
          }
        }
        j++;
      } else {
        if (j - i < max) {
          max = j - i;
          ans = s.substring(i, j);
        }
        if (map.containsKey(s.charAt(i))) {
          map.replace(s.charAt(i), map.get(s.charAt(i)) + 1);
          if (map.get(s.charAt(i)) == 1) {
            count++;
          }
        }
        i++;
      }
    }

    return ans;
  }
}
